The present invention relates to digital communications systems. More particularly, the present invention relates to a method and apparatus for decoding M-array Phase Shift Keying (M-PSK) turbo code using a new approximation technique.
Referring first to FIG. 1, a typical digital communications system 10 has a signal transmission portion 11, a communication channel 13 on a communication medium, and receiving portion 15. The signal transmission portion 11 includes an encoder 17, a puncturing module 19, and a modulator 21. Similarly, the receiving portion 15 includes a demodulator 23, a depuncturing module 25, and a decoder 27. The communication channel 13 used for the transmission may be a microwave radio link, a satellite channel, a digital subscriber loop, or the like.
Digital data, (message bits) from a digital source 29 is received and encoded by the encoder 17 and is then sent to the modulator 21 thorough puncturing module 19. The encoder 17 may be a convolutional encoder. Convolutional encoders are used to encode digital signals so as to maximize the signal to noise ratio (SNR) of the encoded signals when transmitted through a transmission channel or equivalent transmission medium. Convolutional codes include redundant-bits (or parity-check bits) to increase the SNR. This redundancy minimizes the probability of errors introduced during encoding and/or transmission through the communication channel.
A convolutional encoder is defined by the number of coded bits per symbol (CBPS) that it produces, or by its code rate. For example, a rate-1/2 convolutional encoder outputs two bits for every one input bit to generate a stream of convolutional code. It may have 2 CPBS, where it outputs a 2-bit codeword or 2-bit symbol for every input bit. Similarly, a rate-1/n convolutional encoder outputs n bits per one input bit, and a rate-k/n convolutional encoder processes k input bits at a time and outputs n bits for every k input bits.
Such convolutional coding techniques decrease the rate of the signals that may be transmitted over a given bandwidth due to the redundant bits added to the message bits. However, if the channel conditions are favorable, some of the coded output bits may be removed in a systematic way so as to increase the rate of the transmitted bits. This process is called xe2x80x9cpuncturing.xe2x80x9d Prior to digital signal transmission, puncturing is typically used to remove redundancy in a codeword.
The puncturing module 19 provides punctured data to the modulator 21. As described above, coded bits are systematically deleted or xe2x80x9cpuncturedxe2x80x9d in the puncturing module 19. Puncturing may be performed at various rates with respect to the basic unpunctured code. For example, as shown in FIG. 2, a punctured code rate of 3/4 of a system with a basic rate-2/1 encoder is achieved as follows. A rate-1/2 encoder 31 outputs two coded bits, or a 2-bit codeword (Ck0, Ck1) for one input bit (uk). (FIG. 2 shows the situation where k=0, 1, 2.) A puncturer 33 systematically deletes 2 coded bits out of every 3 pairs of coded bits (i.e., out of 6 coded bits), resulting in output of 4 coded bits from the system.
Returning to FIG. 1, the modulator 21 modulates the coded digital data stream onto a carrier signal (typically sinusoidal) to produce a modulated signal. In general, the modulation process making the transmission possible involves switching (keying) the amplitude, frequency, or phase of a sinusoidal carrier in some fashion in accordance with the incoming data. There are three basic signaling schemes, known as amplitude shift keying (ASK), frequency shift keying (FSK), and phase shift keying (PSK). The modulator 21 may be a M-array PSK, in which a codeword is mapped onto a corresponding signal point (massage point) in the M-array PSK signal space (i.e.; M-PSK constellation). The modulated signal includes an in-phase (I) component and a quadrature (Q) component in the signal space.
In the receiving portion 15, the modulated signals are received and demodulated by the demodulator 23, resulting in a stream of symbols. When the transmitted signals are punctured, they must be xe2x80x9cde-puncturedxe2x80x9d before decoding. Thus, the stream of symbols is passed to the depuncturing module 25. The decoder 27 decodes the de-punctured symbols by estimating the original digital data from the symbols, and output the decoded digital signals.
Various approaches have been proposed for the construction of powerful codes structured in such a way that decoding has feasible computational complexity. Turbo coding is one of such coding techniques. FIG. 3 illustrates an encoder 40 of a turbo code in its most basic form. The turbo encoder 40 includes two constituent systematic encoders 41 and 43 joined together by means of an interleaver 45.
An interleaver is an input-output mapping device that permutes the ordering of a sequence of symbols from a fixed alphabet in a completely deterministic manner. That is, it takes the symbols at the input and produces identical symbols at the output but in a different temporal order. The interleaver can be of many types, of which the periodic and pseudo-random are two. Turbo codes use a pseudo-random interleaver, which operates only on the systematic bits.
Typically, but not necessarily, the same code is used for both constituent encoders 41 and 43. The constituent codes recommended for turbo codes are short constraint-length recursive systematic convolutional (RSC) codes. The reason for making the convolutional codes recursive (i.e., feeding one or more of the tap outputs in the sift register back to the input) is to make the internal state of the shift register depend on past outputs. This affects the behavior of the error patterns (a single error in the systematic bits produces an infinite number of parity errors), with the result that a better performance of the overall coding strategy is attained.
In FIG. 2 the input data stream is applied directly to the first encoder 41, and the pseudo-randomly reordered (i.e., interleaved) version of the same data stream is applied to the second encoder 43. The systematic bits (i.e., original message bits) x and the two sets of parity-check bits z1 and z2 generated by the two encoders constitute the output of the turbo encoder 40. Although the constituent codes are convolutional, in reality turbo codes are block codes with the block size being determined by the size of the interleaver.
As discussed above, the parity check bits generated by the two encoders may be punctured prior to data transmission over the channel to maintain a lower code rate. A punctured code is constructed by deleting certain parity check bits, thereby increasing the data rate. However, the use of puncture map is not a necessary requirement of the generation of turbo codes.
FIG. 4 shows the basic structure of a turbo decoder 50. The turbo decoder operates on xe2x80x9cnoisyxe2x80x9d versions of the systematic bits u and the two sets of parity-check bits xcex61 and xcex62. The turbo decoder 50 includes two decoding stages to produce an estimate of the original message bits. Each of two decoding stages uses a BCJR algorithm, which was originally developed by Bahl, Cocke Jelinek, and Raviv (hence the name) to solve a maximum a posteriori probability (MAP) detection problem.
The BCJR algorithm is a soft input-soft output decoding algorithm with two recursions, one forward and the other backward, both of which involve soft decisions. The BCJR algorithm is a MAP decoding in which the bit errors are minimized by estimating the a posteriori probabilities of the individual bits in a code word. That is, to reconstruct the original data sequence, the soft outputs of the BCJR algorithm are hard-limited.
In the case where the transmitted signal has been modulated with M-array PSK, the received signal also has an in-phase (I) component and a quadrature (Q) component. Thus, in the receiver end, a demodulator will generate an (I, Q) pair for each received signal point. In order to use a binary turbo code decoder, therefore, probability information for each of the received bits has to be extracted from the (I,Q) pair of the received signal point. Such probability information requires calculation of Euclidian distance di between the received signal point and the message points (Ii, Qi) in M-array PSK constellation (for i=0, 1, . . . Mxe2x88x921). Typically, for an additive white Gaussian noise (AWGN)channel, such probability information is expressed by reliability information R defined by   R  =      log    ⁡          (                        (                                    ∑              i                        ⁢                          exp              ⁢                              xe2x80x83                            ⁢                              (                                                      -                                                                  E                        s                                                                    N                        0                                                                              ⁢                                      (                                                                                            (                                                      I                            -                                                          I                              i                                                                                )                                                2                                            +                                                                        (                                                      Q                            -                                                          Q                              i                                                                                )                                                2                                                              )                                                  )                                              )                /                  (                                    ∑              j                        ⁢                          exp              ⁡                              (                                                      -                                                                  E                        s                                                                    N                        0                                                                              ⁢                                      (                                                                                            (                                                      I                            -                                                          I                              j                                                                                )                                                2                                            +                                                                        (                                                      Q                            -                                                          Q                              j                                                                                )                                                2                                                              )                                                  )                                              )                    )      
where i is summation for subset of M, and j is summation for another subset of M.
However, in VLSI implementation, calculation of Euclidian distance, as well as calculation of exponential and logarithm functions, is complicated and expensive operation. Therefore, there is a need for simplifying computation in turbo decoders in decoding PSK symbols.
The method of the present invention decodes a received symbol representing data bits including message bits and parity-check bits. The method comprising (a) mapping the symbol onto a received signal point in a signal space, the signal point having an in-phase component (I) and a quadrature phase component (Q) in the signal space; (b) computing reliability information for each data bit, the reliability information associated with a distance di={square root over ((Ixe2x88x92Ii)2+(Qxe2x88x92Qi)2)} between the received signal point (I, Q) and a reference constellation point (Ii, Qi) in the signal space, where i=0, 1, . . . , Mxe2x88x921 (for M an integer), by replacing calculation of (Ixe2x88x92Ii)2+(Qxe2x88x92Qi)2 with calculation of xe2x88x922(Iixc3x97I+Qixc3x97Q); (c) decoding the received symbol using the reliability information and a priori information to produce estimated message bits, the a priori information having a predetermined value in a first decoding; (d) calculating difference between received message bits and the estimated message bits to produce extrinsic information of estimated message bits; and (e) repeating at least once the mapping, computing, decoding and calculating, using the extrinsic information produced in a preceding calculating as the a priori information.